/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-04-01 09:44:55
 * @LastEditors: lily
 * @LastEditTime: 2021-04-01 11:23:11
 */
/*
 * @lc app=leetcode.cn id=617 lang=javascript
 *
 * [617] 合并二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {TreeNode}
 */

//  思路：
//  树的递归只关注当前节点！ 
//  只要有一个树不存在就返回另一个，如果两棵树节点都存在，将节点的值相加存于其中一棵树，分别遍历左右子树得到结果树的左右子树。

//  复杂度：O(min(m,n))  O(min(m,n))    m 和 n分别是两个二叉树的节点个数。

var mergeTrees = function (root1, root2) {
    // let root = new TreeNode()
    // if (root1 && root2) {
    //     root.val = root1.val + root2.val
    //     if (root1.left || root2.left) {
    //         root.left = mergeTrees(root1.left, root2.left)
    //     }
    //     if (root1.right || root2.right) {
    //         root.right = mergeTrees(root1.right, root2.right)
    //     }
    //     return root
    // } else if (!root1) {
    //     return root2
    // } else if (!root2) {
    //     return root1
    // }

    // 不新增树
    if (!root1 || !root2) {
        return root1 || root2
    }
    root1.val += root2.val
    root1.left = mergeTrees(root1.left, root2.left)
    root1.right = mergeTrees(root1.right, root2.right)
    return root1

};
// @lc code=end
function TreeNode(val, left, right) {
    this.val = (val === undefined ? 0 : val)
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
}

let tree1 = new TreeNode(1, new TreeNode(3, new TreeNode(5)), new TreeNode(2))
let tree2 = new TreeNode(2, new TreeNode(1, null, new TreeNode(4)), new TreeNode(3, null, 7))
mergeTrees(tree1, tree2)